//
//  二叉树.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/1/30.
//

import UIKit

class TreeNode<E: Equatable> {
    var left: TreeNode?
    var right: TreeNode?
    var parent: TreeNode?
    var val: E
    init(_ elem: E) {
        val = elem
    }

    init(elem: E, left: TreeNode? = nil, right: TreeNode? = nil, parent: TreeNode? = nil) {
        self.val = elem
        self.left = left
        self.right = right
        self.parent = parent
    }
    func hasTowChildNode() -> Bool {
        return right != nil && left != nil
    }
    func isLeafNode() -> Bool {
        return left == nil && right == nil
    }
    func isLeftChild() -> Bool {
        (parent != nil && parent?.left == self)
    }
    func isRightChild() -> Bool {
        (parent != nil && parent?.right == self)
    }
}

extension TreeNode: Equatable {
    static func == (lhs: TreeNode, rhs: TreeNode) -> Bool {
        lhs.val == rhs.val
    }
}

/// 二叉树
/// 1、所有节点的度都<=2
/// 2、左右子树是有顺序的
class BinaryTree<E: Equatable & Comparable> {
    
    
    var count = 0
    var rootNode: TreeNode<E>?
    /// 元素数量
    /// - Returns: 数据
    func size() -> Int {
        count
    }
    /// 是否是空树
    /// - Returns: 结果
    func isEmpty() -> Bool {
        count == 0
    }
    
    /// 清空二叉树
    func clear() {
        rootNode = nil
        count = 0
    }
    
}
/// 遍历二叉树
extension BinaryTree {
    //    前序遍历二叉树（递归）根节点、左子树、右子树
    func qianxu(_ node: TreeNode<E>?) {
        guard let node = node else {
            return
        }
        print(node.val)
        qianxu(node.left)
        qianxu(node.right);
    }
    //    中序遍历 中间访问根节点
    func zhongxu(_ node: TreeNode<E>?) {
        guard let node = node else {
            return
        }
        zhongxu(node.left)
        print(node.val)
        zhongxu(node.right)
    }
    //    后续遍历 最后访问根节点
    func houxu(_ node: TreeNode<E>?) {
        guard let node = node else {
            return
        }
        houxu(node.left)
        houxu(node.right)
        print(node.val)
    }
    //     非递归是先前序遍历（需要使用栈）
    func qianxu1(_ node: TreeNode<E>?) {
        var stack = [TreeNode<E>]() // 先进后出
        var node = node
        while true {
            if let temp = node {
                print(temp.val)
                if let right = temp.right {
                    stack.append(right)
                }
                node = temp.left
            } else if stack.isEmpty {
                return
            } else {
                node = stack.removeLast()
            }
        }
        
    }
    func qianxu2(_ node: TreeNode<E>) {
        var stack = [TreeNode<E>]() // 先进后出
        stack.append(node)
        while !stack.isEmpty {
            let node = stack.removeLast()
            print(node.val)
            if let right = node.right  {
                stack.append(right)
            }
            if let left = node.left {
                stack.append(left)
            }
            
        }
        
    }
    func hongxu1(_ node: TreeNode<E>?) {
        var stack = [TreeNode<E>]()
        var node = node
        while true {
            if let temp = node {
                stack.append(temp)
                node = temp.left
            } else if stack.isEmpty {
                return
            } else {
                node = stack.removeLast()
                print(node?.val)
                node = node?.right
            }
        }
    }
    
    //    后续遍历 最后访问根节点
    func houxu1(_ node: TreeNode<E>) {
        var stack = [TreeNode<E>]()
        var prev: TreeNode<E>?
        stack.append(node)
        while let top = stack.last {
            if (top.isLeafNode()) || (prev?.parent == top) {
                prev = stack.removeLast()
                print(prev)
            } else {
                if let right = top.right {
                    stack.append(right)
                }
                if let left = top.right {
                    stack.append(left)
                }
            }
        }
        
    }
    
    //    层序遍历 从左到右一层一层的访问
    func cengxu(_ node: TreeNode<E>?) {
        guard let node = node else {
            return
        }
        let queue:Queue<TreeNode<E>> = Queue()
        queue.push(elem: node)
        while let temp = queue.pop() {
            print(temp.val)
            if let left = temp.left {
                queue.push(elem: left)
            }
            if let right = temp.right{
                queue.push(elem: right)
            }
        }
    }
    //    S型遍历(还有实现)
    func sxingPrint(_ node: TreeNode<E>?) {
        guard let node = node else {
            return
        }
        var queue = Array<TreeNode<E>>()
        queue.append(node)
        //        var level = 0 // 层
        //        var size = 1
        while !queue.isEmpty {
            let temp = queue.removeFirst()
            print(temp.val)
            if let left = temp.left {
                queue.append(left)
            }
            if let right = temp.right{
                queue.append(right)
            }
        }
    }
}
/**
 前驱和后继结点
 */
extension BinaryTree {
    /// 获取前驱节点（中序遍历中，在当前节点前的一个节点）
    /// - Parameter node: 目标节点
    /// - Returns: 目标节点的前驱节点
    func predesessor(_ node: TreeNode<E>?) -> TreeNode<E>? {
        guard let node = node else {
            
            return nil
        }
        // 从子节点中寻找
        if let left = node.left {
            var p: TreeNode<E> = left
            while let right = p.right{
                p = right
            }
            return p
        }
        // 从父节点中寻找
        var p = node
        while let parent = p.parent, p == parent.left {
            p = parent
        }
        // 父节点为nil 或 p == parent.right
        return p.parent
    }
    
    /// 后继节点
    /// - Parameter node: 目标节点
    /// - Returns: 目标节点的后继节点
    func successor(_ node: TreeNode<E>?) -> TreeNode<E>? {
        guard let node = node else {
            return nil
        }
        
        // 从子节点中寻找
        if let right = node.right {
            var p: TreeNode<E> = right
            while let left = p.left{
                p = left
            }
            return p
        }
        // 从父节点中寻找
        var p = node
        while let parent = p.parent, p == parent.right {
            p = parent
        }
        // 父节点为nil 或 p == parent.right
        return p.parent
    }
}
//    打印二叉树
extension BinaryTree {

    static func printBinaryTree(_ rootNode: TreeNode<E>?) {
        print("打印树****************************打印树")
        toString(rootNode, prefix: "")
    }
    
    static func toString(_ node: TreeNode<E>?, prefix: String) {
        guard let node = node else { return }
//        let str = node.parent?.val != nil ? "\(node.parent!.val)" : "nil"
//        let result = prefix + "\(node.val)" + "_" + str
        let result = prefix + "\(node.val)"
        print(result)
        var temp = ""
        for _ in  prefix {
            temp = temp + " "
        }
        toString(node.right, prefix: temp + "|___R___")
        let prefix =  temp +  "|___L___"
        toString(node.left, prefix: prefix)
    }
    
}
//    获取某个结点
extension BinaryTree {

        func getNode(_ val: E, _ root: TreeNode<E>?) -> TreeNode<E>? {
            guard let node = root else {
                return nil
            }
            let queue:Queue<TreeNode<E>> = Queue()
            queue.push(elem: node)
            while let temp = queue.pop() {
                if temp.val == val {
                    return temp
                }
                if let left = temp.left {
                    queue.push(elem: left)
                }
                if let right = temp.right{
                    queue.push(elem: right)
                }
            }
            return nil
        }
}

extension BinaryTree {
    
    /// 以满二叉树的方式生成二叉树
    func creatBinaryTree(_ array: [Int]) -> TreeNode<Int> {
        let root = creat(array, 0)
        return root
    }
    
    func creat(_ array: [Int], _ i: Int)  -> TreeNode<Int>  {
        let node = TreeNode(array[i])
        let left =  2 * i + 1
        let right = 2 * i + 2
        if node.val == 4 {
            print(left, right)
        }
        if left < array.count && array[left] >= 0 {
            node.left = creat(array, left)
        }
        if right < array.count && array[right] >= 0 {
            node.right = creat(array, right)
        }
        return node
    }
    
    
}
